package com.hsc.offer.tre;

/**
 * @author
 * @date 2025-06-10
 * @Description 二叉树还原
 * 4.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 */
public class ReConstructBinaryTree {

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode treeNode = new ReConstructBinaryTree().reConstructBinaryTree(pre, in);
        System.out.println(treeNode.val);
    }

    /**
     * 输入前序遍历和中序遍历 然后还原二叉树
     * 前序遍历规则:根左右
     * 中序遍历规则：左根右
     * 后序遍历规则：左右根
     *
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        // 严谨性判断
        if (pre == null || in == null || pre.length == 0 || in.length == 0) {
            return null;
        }

        // 1、创建一个根节点 通过前序遍历的第一个元素得到根节点对应的值  {1,2,4,7,3,5,6,8} 也就是 2
        // 当前的根节点
        TreeNode root = new TreeNode(pre[0]);
        // 根据中序遍历{4,7,2,1,5,3,8,6} 的结果找到根节点的位置
        for (int i = 0; i < in.length; i++) {
            // 2、根据中序序列 找到根节点的索引值
            if (in[i] == root.val) {
                // 说明找到了根节点的索引 值i
                // 获取根节点的左子树的值
                // 左子树的前序遍历 ：左子树的值 i=1 的数组下标值为 2 刚好他的左子树的值长度也是 2
                // 所以i就是我们需要计算的长度
                int[] preLeft = new int[i];
                // 装载左子树对应的中序遍历的值
                int[] inLeft = new int[i];
                // 拿到了左子树的前序遍历和中序遍历 继续寻找 左子树的根节点 以及左子树对应左子树和右子树
                // 所以这是一个递归的过程
                // 3、获取左子树对应值数组 上面确定了元素容量的大小
                // 得到左子树的前序序列 注意这里拷贝的是pre
                System.arraycopy(pre, 1, preLeft, 0, i);// 进行拷贝：原数组，原数组的起点，目的数组，目的数组的起点，长度
                // 得到左子树的中序序列 这里拷贝的是 in
                System.arraycopy(in, 0, inLeft, 0, i);
                // 递归调用获取左子树
                TreeNode leftTree = reConstructBinaryTree(preLeft, inLeft);

                // 4、处理根节点的右子树
                // 拿到右子树的前序序列和中序序列的数组大小
                // 拿到右子树的前序序列 i的值是根据中序遍历得出的索引值 当前的根节点为 1  中序序列中 1 的元素位置为i=3  。所以得出右子树的的元素个树等于=数组的长度-左子树的元素个数-根节点的元素个数=pre.length-i-1
                int[] preRight = new int[pre.length - i - 1];
                int[] inRight = new int[in.length - i - 1];
                // 拿到右子树的前序序列开始位置为：i+1 开始之后的元素都是右子树元素[i + 1,pre.length - i - 1]
                System.arraycopy(pre, i + 1, preRight, 0, pre.length - i - 1);// 进行拷贝：原数组，原数组的起点，目的数组，目的数组的起点，长度
                // 拿到右子树的中序序列
                System.arraycopy(in, i + 1, inRight, 0, in.length - i - 1);// 进行拷贝：原数组，原数组的起点，目的数组，目的数组的起点，长度
                // 传入右子树的前序和中序 得到一个右子树
                TreeNode rightTree = reConstructBinaryTree(preRight, inRight);
                //  将左子树设置给根节点
                root.left = leftTree;
                root.right = rightTree;
                return root;
            }
        }
        // 整个树构建完成
        return root;
    }

}


/**
 * 数节点
 */
class TreeNode {
    // 具体的值
    int val;
    // 树的左节点引用
    TreeNode left;
    // 树的右节点引用
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

}
